package com.example.algorithm.manacher;

/**
 * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
 *  说明：本题中，我们将空字符串定义为有效的回文串。
 *
 *  示例 1:
 * 输入: "A man, a plan, a canal: Panama"
 * 输出: true
 * 解释："amanaplanacanalpanama" 是回文串
 *
 *  示例 2:
 * 输入: "race a car"
 * 输出: false
 * 解释："raceacar" 不是回文串
 *
 *  提示：
 *  1 <= s.length <= 2 * 105
 *  字符串 s 由 ASCII 字符组成
 */
public class Leetcode125_IsPalindrome {
    public static void main(String[] args) {
        System.out.println(new Solution().isPalindrome("A man, a plan, a canal: PanAma"));

    }

    static class Solution {
        /**
         * 双指针在原字符串上进行判断
         *
         * @param s
         * @return
         */
        private boolean isPalindrome2(String s) {
            if (s.length() <= 1)
                return true;
            int left = 0, right = s.length() - 1;
            char[] chars = s.toCharArray();

            while (left <= right) {
                while (left < right && !Character.isLetterOrDigit(chars[left])) {
                    left++;
                }

                while (left < right && !Character.isLetterOrDigit(chars[right])) {
                    right--;
                }

                if (left <= right) {
                    if (Character.toLowerCase(chars[left]) != Character.toLowerCase(chars[right]))
                        return false;
                    left++;
                    right--;
                }

            }
            return true;
        }
        /**
         * 方法一:筛选+双指针
         * @param s
         * @return
         */
        private boolean isPalindrome1(String s) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
//                if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
//                    sb.append(s.charAt(i));
//                }
                if (Character.isLetterOrDigit(c)) {
                    sb.append(Character.toLowerCase(c));
                }
            }

            char[] chars = sb.toString().toCharArray();
            int left = 0, right = chars.length - 1;
            while (left <= right) {
                if (chars[left++] != chars[right--])
                    return false;
            }
            return true;

        }

        public boolean isPalindrome(String s) {
            return isPalindrome2(s);
        }
    }
}
